// @before-stub-for-debug-begin
#include "commonInc.h"
// @before-stub-for-debug-end

/*
 * @lc app=leetcode.cn id=49 lang=cpp
 *
 * [49] 字母异位词分组
 */

class Solution_0 {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) 
    {
        //将strs中的每个串转换为 'a3b1c4' 的格式,表示每种字符出现的频次
        std::vector<int> charsFreq(26,0);

        std::unordered_map<string,vector<string>> ansGroups;
        for(const string& str : strs)
        {
            memset(&charsFreq[0],0,sizeof(int)*charsFreq.size());
            for(char ch : str)
            {
                charsFreq[ch-'a']++;
            }

            string strHashKey="";
            for(int i=0;i<charsFreq.size();++i)
            {
                if(charsFreq[i] > 0)
                {
                    strHashKey+=i+'a';
                    strHashKey+= std::to_string(charsFreq[i]);
                }
            }
            ansGroups[strHashKey].push_back(str);
        }

        vector<vector<string>> ans;
        for(auto iter=ansGroups.begin();iter!=ansGroups.end();++iter)
        {
            ans.emplace_back(iter->second);
        }
        return ans;
    }
};

// @lc code=start
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) 
    {
        auto hashFuc=[fn=hash<int>{}](const array<int,26>& arr)->size_t
        {
            return std::accumulate(arr.begin(),arr.end(),0u,
            [&](size_t acc,int num)
            {
                return (acc<<1) ^ fn(num);
            });
        };

        array<int,26> charsFreq;
        std::unordered_map<array<int,26>,vector<string>,decltype(hashFuc)> anagramGroups(0,hashFuc);
        for(auto& str : strs)
        {
            memset(&charsFreq[0],0,sizeof(int)*charsFreq.size());
            for(char ch : str)
            {
                charsFreq[ch-'a']++;
            }
            anagramGroups[charsFreq].push_back(str);
        }

        vector<vector<string>> ans;
        for(auto iter=anagramGroups.begin();iter!=anagramGroups.end();++iter)
        {
            ans.emplace_back(iter->second);
        }
        return ans;
    }
};
// @lc code=end

